package LeetCode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author self
 * @Date 2024/10/20 16:37
 * @Describe 20. 有效的括号
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 *
 *
 * 示例 1：
 *
 * 输入：s = "()"
 *
 * 输出：true
 *
 * 示例 2：
 *
 * 输入：s = "()[]{}"
 *
 * 输出：true
 *
 * 示例 3：
 *
 * 输入：s = "(]"
 *
 * 输出：false
 *
 * 示例 4：
 *
 * 输入：s = "([])"
 *
 * 输出：true
 *
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 仅由括号 '()[]{}' 组成
 */
public class Code20_isValid {

    /**
     * 判断输入的字符串中的括号是否有效
     * 有效字符串中的括号必须是闭合的，并且左括号必须以正确的顺序关闭
     *
     * @param s 输入的字符串，包含括号字符
     * @return 如果字符串中的括号有效，则返回true；否则返回false
     */
    public boolean isValid(String s) {
        // 空字符串被认为是有效的
        if (s == null || s.length() == 0) {
            return true;
        }

        // 使用HashMap存储括号对，便于快速查找对应的左括号
        HashMap<Character, Character> patternMap = new HashMap<>();
        patternMap.put(')', '(');
        patternMap.put(']', '[');
        patternMap.put('}', '{');

        // 使用栈作为辅助结构，用于暂存遇到的左括号
        Stack<Character> stack = new Stack<>();
        int length = s.length();

        // 遍历字符串中的每个字符
        for (Character c: s.toCharArray()) {
            // 如果是左括号，则压入栈中
            if (patternMap.containsValue(c)) {
                stack.push(c);
            } else { // 如果是右括号，则进行判断
                // 如果栈为空或者栈顶的左括号与当前右括号不匹配，则字符串无效
                if (stack.isEmpty() || stack.pop() != patternMap.get(c)) {
                    return false;
                }
            }
        }
        // 如果栈为空，则说明所有的左括号都找到了匹配的右括号，字符串有效
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String s = "()";
        Code20_isValid code20_isValid = new Code20_isValid();
        boolean valid = code20_isValid.isValid(s);
        System.out.println(valid);
    }
}
